package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         200,
		Discription: "岛屿数量",
		Level:       2,
		Labels: map[string]int{
			"图连通性": 1,
			"中间态": 1,
		},
	})
}

// NumIslands 遍历矩阵，碰到1就把dfs能联通的1置为0（包括自己），然后count++
//  @param grid
//  @return int
func NumIslands(grid [][]byte) int {
	m := len(grid)
	n := len(grid[0])
	dirs := [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
	var dfs func(int, int)
	dfs = func(i, j int) {
		for _, dir := range dirs {
			x := i + dir[0]
			y := j + dir[1]
			if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == '0' {
				continue
			}

			grid[x][y] = '0'
			dfs(x, y)
		}
	}

	count := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				count++
				dfs(i, j)
			}
		}
	}

	return count
}
